/*
 * Kodkod -- Copyright (c) 2005-present, Emina Torlak
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package kodkod.util.collections;

import java.util.AbstractSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Provides utility methods for working with arrays and collections.
 *
 * @author Emina Torlak
 */
public final class Containers {

    private static Comparator<Object> identityComparator;
    private static Comparator<Object> hashComparator;

    private Containers() {}

    /**
     * Returns a new iterator over the given array of items. The iterator is backed
     * by the given array. The contents of the array are not modified by the
     * iterator. The effect of this method is the same as calling
     * Iterators.iterator(0, items.length, items).
     *
     * @throws NullPointerException items = null
     */
    @SafeVarargs
    public static final <T, E extends T> Iterator<T> iterate(final E... items) {
        return new AscendingArrayIterator<T>(0, items.length, items);
    }

    /**
     * Returns a new iterator over the given array of items. The iterator is backed
     * by the given array. The contents of the array are not modified by the
     * iterator. The returned iterator enumerates the items located between indeces
     * start, inclusive, and end, exclusive. If start < end, the elements are
     * returned in the ascending order; otherwise, they are returned in the
     * descending order.
     *
     * @throws NullPointerException items = null
     * @throws IllegalArgumentException start < end && (start < 0 || end >
     *             items.length) || start > end && (start >= items.length || end <
     *             -1)
     */
    @SafeVarargs
    public static final <T, E extends T> Iterator<T> iterate(int start, int end, final E... items) {
        if (start < end)
            return new AscendingArrayIterator<T>(start, end, items);
        else if (start > end)
            return new DescendingArrayIterator<T>(start, end, items);
        else
            return emptyIterator();
    }

    /**
     * Returns an iterator that has no elements. That is, calls to hasNext will
     * return false, and all other calls will result in a runtime exception.
     *
     * @return an empty iterator
     */
    @SuppressWarnings("unchecked" )
    public static final <T> Iterator<T> emptyIterator() {
        return (Iterator<T>) Collections.emptySet().iterator();
    }

    /**
     * Calls System.arraycopy(src, srcPos, dest, destPos, length) and returns the
     * destination array.
     *
     * @ensures System.arraycopy(src, srcPos, dest, destPos, length)
     * @return dest
     */
    public static final <T> T[] copy(T[] src, int srcPos, T[] dest, int destPos, int length) {
        System.arraycopy(src, srcPos, dest, destPos, length);
        return dest;
    }

    /**
     * Calls System.arraycopy(src, 0, dest, 0, src.length) and returns the
     * destination array.
     *
     * @requires dest.length >= src.length
     * @ensures System.arraycopy(src, 0, dest, 0, src.length)
     * @return dest
     */
    public static final <T> T[] copy(T[] src, T[] dest) {
        System.arraycopy(src, 0, dest, 0, src.length);
        return dest;
    }

    /**
     * Returns a comparator that compares objects according to their
     * {@link System#identityHashCode(Object) identity hashcodes}.
     *
     * @return a comparator that compares objects according to their
     *         {@link System#identityHashCode(Object) identity hashcodes}.
     */
    public static final Comparator<Object> identityComparator() {
        if (identityComparator == null) {
            identityComparator = new Comparator<Object>() {

                @Override
                public int compare(Object o1, Object o2) {
                    final int c1 = System.identityHashCode(o1);
                    final int c2 = System.identityHashCode(o2);
                    return c1 == c2 ? 0 : (c1 < c2 ? -1 : 1);
                }
            };
        }
        return identityComparator;
    }

    /**
     * Returns 0 if o is null, otherwise returns o.hashCode().
     *
     * @return o=null => 0, o.hashCode()
     */
    static final int hash(Object o) {
        return o == null ? 0 : o.hashCode();
    }

    /**
     * Returns true if both o1 and o2 are null or if o1.equals(o2)
     *
     * @return true if both o1 and o2 are null or if o1.equals(o2)
     */
    static final boolean eq(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
    }

    /**
     * Returns a comparator that compares objects according to their
     * {@link Object#hashCode() hashcodes}. The null reference is considered to have
     * a hashcode of 0.
     *
     * @return a comparator that compares objects according to their
     *         {@link Object#hashCode() hashcodes}.
     */
    public static final Comparator<Object> hashComparator() {
        if (hashComparator == null) {
            hashComparator = new Comparator<Object>() {

                @Override
                public int compare(Object o1, Object o2) {
                    final int c1 = hash(o1);
                    final int c2 = hash(o2);
                    return c1 == c2 ? 0 : (c1 < c2 ? -1 : 1);
                }
            };
        }
        return hashComparator;
    }

    /**
     * Calls {@link java.util.Arrays#sort(Object[], Comparator)} on the given array
     * and returns it. The elements are sorted in the ascending order of their
     * identity hashcodes.
     *
     * @ensures java.util.Arrays.sort(array, {@link #identityComparator()})
     * @return the given array, with its elements sorted in the increasing order of
     *         identity hashcodes
     */
    public static final <T> T[] identitySort(T[] array) {
        java.util.Arrays.sort(array, identityComparator());
        return array;
    }

    /**
     * Calls {@link java.util.Arrays#sort(Object[], Comparator)} on the given array
     * and returns it. The elements are sorted in the ascending order of their
     * hashcodes.
     *
     * @ensures java.util.Arrays.sort(array, {@link #hashComparator()})
     * @return the given array, with its elements sorted in the increasing order of
     *         hashcodes
     */
    public static final <T> T[] hashSort(T[] array) {
        java.util.Arrays.sort(array, hashComparator());
        return array;
    }

    /**
     * Searches the specified array for the specified object using the binary search
     * algorithm and reference equality. The array must be sorted into ascending
     * order according to the identity hashcodes of its elements (as by
     * {@link #identitySort(Object[])}) prior to making this call. If it is not
     * sorted, the results are undefined. If the array contains multiple occurences
     * of the specified object, there is no guarantee which one will be found.
     *
     * @requires all i, j: [0..array.length) | i < j => array[i].hashCode() <=
     *           array[j].hashCode())
     * @return index of the search key, if it is contained in the array; otherwise,
     *         (-(insertion point) - 1). The insertion point is defined as the point
     *         at which the key would be inserted into the array: the index of the
     *         first element greater than the key, or array.length, if all elements
     *         in the array are less than the specified key. Note that this
     *         guarantees that the return value will be >= 0 if and only if the key
     *         is found.
     */
    public static final int identityBinarySearch(Object[] array, Object key) {
        int low = 0;
        int high = array.length - 1;
        int index = System.identityHashCode(key);

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midIndex = System.identityHashCode(array[mid]);
            if (midIndex < index)
                low = mid + 1;
            else if (midIndex > index)
                high = mid - 1;
            else { // index found, now check that variables are the same
                if (array[mid] == key)
                    return mid;
                // check all variables with the same index (if any)
                for (int i = mid + 1; i < array.length && System.identityHashCode(array[i]) == index; i++) {
                    if (array[i] == key)
                        return i;
                }
                for (int i = mid - 1; i >= 0 && System.identityHashCode(array[i]) == index; i--) {
                    if (array[i] == key)
                        return i;
                }
                return -(mid + 1); // var not found
            }
        }

        return -(low + 1); // key not found.
    }

    /**
     * Searches the specified array for the specified object using the binary search
     * algorithm and object equality. The array must be sorted into ascending order
     * according to the hashcodes of its elements (as by
     * {@link #hashSort(Object[])}) prior to making this call. If it is not sorted,
     * the results are undefined. If the array contains multiple occurences of the
     * specified object, there is no guarantee which one will be found.
     *
     * @requires all i, j: [0..array.length) | i < j =>
     *           System.identityHashCode(array[i]) <=
     *           System.identityHashCode(array[j])
     * @return index of the search key, if it is contained in the array; otherwise,
     *         (-(insertion point) - 1). The insertion point is defined as the point
     *         at which the key would be inserted into the array: the index of the
     *         first element greater than the key, or array.length, if all elements
     *         in the array are less than the specified key. Note that this
     *         guarantees that the return value will be >= 0 if and only if the key
     *         is found.
     */
    public static final int hashBinarySearch(Object[] array, Object key) {
        int low = 0;
        int high = array.length - 1;
        int index = hash(key);

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midIndex = hash(array[mid]);
            if (midIndex < index)
                low = mid + 1;
            else if (midIndex > index)
                high = mid - 1;
            else { // index found, now check that variables are the same
                if (eq(array[mid], key))
                    return mid;
                // check all variables with the same index (if any)
                for (int i = mid + 1; i < array.length && hash(array[i]) == index; i++) {
                    if (eq(array[i], key))
                        return i;
                }
                for (int i = mid - 1; i >= 0 && hash(array[i]) == index; i--) {
                    if (eq(array[i], key))
                        return i;
                }
                return -(mid + 1); // var not found
            }
        }

        return -(low + 1); // key not found.
    }

    /**
     * Returns an identity set backed by the given array (i.e. a set that uses
     * reference equality for comparisons). The array must contain no duplicates,
     * its elements must be sorted in the increasing order of identity hashcodes (as
     * by {@link #identitySort(Object[])}), and its contents must not be changed
     * while it is in use by the returned set.
     *
     * @requires all i, j: [0..array.length) | i < j =>
     *           System.identityHashCode(array[i]) <=
     *           System.identityHashCode(array[j])
     * @return an unmodifiable identity Set view of the given array
     */
    public static final <T> Set<T> asIdentitySet(final T[] array) {
        return new AbstractSet<T>() {

            @Override
            public boolean contains(Object o) {
                return identityBinarySearch(array, o) >= 0;
            }

            @Override
            public Iterator<T> iterator() {
                return iterate(array);
            }

            @Override
            public int size() {
                return array.length;
            }

            @Override
            public int hashCode() {
                int result = 0;
                for (Object o : array) {
                    result += System.identityHashCode(o);
                }
                return result;
            }
        };
    }

    /**
     * Returns a set backed by the given array (i.e. a set that uses object equality
     * for comparisons). The array must contain no duplicates, its elements must be
     * sorted in the increasing order of hashcodes (as by
     * {@link #hashSort(Object[])}), and its contents must not be changed while it
     * is in use by the returned set.
     *
     * @requires all i, j: [0..array.length) | i < j => array[i].hashCode() <=
     *           array[j].hashCode
     * @return an unmodifiable Set view of the given array
     */
    public static final <T> Set<T> asHashSet(final T[] array) {
        return new AbstractSet<T>() {

            @Override
            public boolean contains(Object o) {
                return hashBinarySearch(array, o) >= 0;
            }

            @Override
            public Iterator<T> iterator() {
                return iterate(array);
            }

            @Override
            public int size() {
                return array.length;
            }
        };
    }

    /**
     * Returns a new set that contains the asymmetric difference between the left
     * and the right sets.
     *
     * @return some s: Set<T> | s.elements = left.elements - right.elements
     */
    public static final <T> Set<T> setDifference(Set<T> left, Set<T> right) {
        final Set<T> ret = new LinkedHashSet<T>(left);
        ret.removeAll(right);
        return ret;
    }

    /**
     * An unmodifying iterator over an array.
     */
    private static abstract class ArrayIterator<T> implements Iterator<T> {

        final T[] items;
        final int end;
        int       cursor;

        /**
         * Constructs a new iterator over the given array of items. The iterator is
         * backed by the given array. The contents of the array are not modified by the
         * iterator. The constructed iterator returns the items located between the
         * indeces start, inclusive, and end, exclusive.
         *
         * @requires items != null && start < end => end in [0..items.length] && start
         *           in [0..end], start in [0..items.length) && end in [-1..start]
         */
        @SafeVarargs
        <E extends T> ArrayIterator(int start, int end, final E... items) {
            this.items = items;
            this.cursor = start;
            this.end = end;
        }

        @Override
        public final void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * An ascending iterator over an array.
     */
    private static final class AscendingArrayIterator<T> extends ArrayIterator<T> {

        /**
         * Constructs a new iterator over the given array of items.
         *
         * @requires items != null && start < end
         * @throws IllegalArgumentException start < 0 || end > items.length
         */
        <E extends T> AscendingArrayIterator(int start, int end, E[] items) {
            super(start, end, items);
            if (start < 0 || end > items.length) {
                throw new IllegalArgumentException("start < end && (start < 0 || end > items.length)");
            }
        }

        @Override
        public boolean hasNext() {
            return cursor >= 0 && cursor < end;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            return items[cursor++];
        }
    }

    /**
     * A descending iterator over an array.
     */
    private static final class DescendingArrayIterator<T> extends ArrayIterator<T> {

        /**
         * Constructs a new iterator over the given array of items.
         *
         * @requires items != null && start > end
         * @throws IllegalArgumentException start >= items.length || end < -1
         */
        <E extends T> DescendingArrayIterator(int start, int end, E[] items) {
            super(start, end, items);
            if (start >= items.length || end < -1) {
                throw new IllegalArgumentException("start > end && (start >= items.length || end < -1)");
            }
        }

        @Override
        public boolean hasNext() {
            return cursor > end;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            return items[cursor--];
        }

    }

}
